

/**
 * 经典动态规划题目：
 * 有数量不限的硬币，币值为25分、10分、5分和1分，
 * 请编写代码计算n分有几种表示法。
 */
public class Coins {
	public static void main(String[] args) {
		int n = 5;
		Coins coins = new Coins();
		System.out.println(coins.countWays(n));
	}

	public int countWays(int n) {
		int[] coins = {1, 5, 10, 25};
		int[] dp = new int[n + 1];
		//1分只有一种方案
		dp[1] = 1;
		for (int j = 0; j < coins.length; j++) {
			for (int i = 2; i < dp.length; i++) {
				if (coins[j]<=n){
					dp[i]=dp[i-coins[j]];
				}
			}
		}
		return dp[n];
	}
}
